package kmp;

import java.util.Arrays;

/**
 * "部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例，
 *  － "A"的前缀和后缀都为空集，共有元素的长度为0；
 *  －"AB"的前缀为[A]，后缀为[B]，共有元素的长度为0； 
 *  － "ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0； 
 *  －"ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0； 
 *  － "ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A"，长度为1；
 *  － "ABCDAB"的前缀为[A, AB, ABC, ABCD,ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB"，长度为2； 
 *  － "ABCDABD"的前缀为[A, AB,ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。
 * 
 * "部分匹配"的实质是，有时候，字符串头部和尾部会有重复。比如，"ABCDAB"之中有两个"AB"，
 * 那么它的"部分匹配值"就是2（"AB"的长度）。搜索词移动的时候，第一个"AB"向后移动4位（字符串长度-部分匹配值），
 * 就可以来到第二个"AB"的位置。
 * 
 *  http://kb.cnblogs.com/page/176818/
 * 
 * 	http://blog.csdn.net/yutianzuijin/article/details/11954939/
 *
 */

public class KMP {
	public int[] next(String target) {
		int[] next = new int[target.length()];
		next[0] = 0;
		for (int i = 1; i < target.length(); i++) {
			int k = next[i - 1];
			while (k > 0 && target.charAt(k) != target.charAt(i))
				k = next[k - 1];
			next[i] = target.charAt(k) == target.charAt(i) ? k + 1 : k;
		}
		return next;
	}

	public int search(String src, String target) {
		int[] next = next(target);
		System.out.println(Arrays.toString(next));
		for (int i = 0, j = 0; i < src.length(); i++) {
			while (j != 0 && src.charAt(i) != target.charAt(j))
				j = next[j - 1];
			if (src.charAt(i) == target.charAt(j))
				j++;
			if (j == target.length())
				return i - target.length() + 1;
		}
		return -1;
	}

	public static void main(String[] args) {
		System.out.println(new KMP().search("BBC ABCDAB ABCDABD", "ABCDABD"));
	}
}
